// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-10 09:33
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DateTrain;

import java.util.ArrayList;
import java.util.List;

@SuppressWarnings("ALL")
public class Preorder {
    /**
     * N叉树的前序遍历序列
     * N叉树的前序遍历序列就是其对应二叉树前序遍历序列
     */
    public List<Integer> preorder(Node root) {
        // 观察规律 -> 直接遍历 -> 遍历每一个孩子列表的第一个节点然后从底往上遍历
        List<Integer> ans = new ArrayList<>();
        return preOrderNTree(root, ans);

    }

    /**
     * N叉树的前序遍历
     *
     * @param root
     * @param ans
     * @return
     */
    private List<Integer> preOrderNTree(Node root, List<Integer> ans) {
        if (root == null) {
            return ans;
        }
        ans.add(root.val);
        while (!root.children.isEmpty()) {
            // 当前节点有孩子节点
            Node firstChild = root.children.remove(0);
            preOrderNTree(firstChild, ans);
        }
        return ans;
    }


    // Definition for a TreeNode.
    class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }


}
